#include<bits/stdc++.h>
#define ll long long
#define Max(a,b,c)  max(a,max(b,c))
#define inf 2100000000
#define fa(i,n,k) for(register int i=k;i<=n;i++)

using namespace std;
ll n,Q;
struct sortt {
	ll num,pos;
} a[8850],b[8850];
bool cmp(sortt x,sortt y) {
//	return x.num==y.num ? x.pos<x.pos : x.num<y.num;
	return x.num<y.num;
}
int main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
//	freopen("sort.in","r",stdin);
//	freopen("sort.out","w",stdout);
	scanf("%lld%lld",&n,&Q);
	for(int i=1; i<=n; i++)cin>>a[i].num,a[i].pos=i;
	while(Q--) {
		int f;
		ll x,v;
		cin>>f>>x;
		if(f==1) {
			cin>>v;
			a[x].num=v;
			sort(a+1,a+n+1,cmp);
		} else if(f==2) {
			//put a -> b
			for(int i=1; i<=n; i++)b[i].num=a[i].num,b[i].pos=a[i].pos;
			sort(b+1,b+n+1,cmp);
			//find
			ll mp=inf,mn=inf;
			for(int i=1; i<=n; i++)
				if(b[i].num==a[x].num) {
					for(int j=1;j<=n;j++)cout<<a[j].num<<' '<<a[j].pos<<' ';
					for(int j=1;j<=n;j++)cout<<b[j].num<<' '<<b[j].pos<<' ';
					cout<<endl;
					cout<<i<<endl;
//					mp=min(b[i].pos,mp);
//					if(mp>b[i].pos)mn=b[i].num,mp=b[i].pos;
					break;
				}
//			cout<<mp<<endl;
		}
	}
	return 0;
}

